"""
https://leetcode.cn/problems/count-subarrays-with-majority-element-ii/
"""

class Solution:
  def countMajoritySubarrays(self, nums: List[int], target: int) -> int:
    # 将 nums 中等于 target 的数视为 1 ，否则视为 -1，题目转换为计算 nums 中元素和严格大于 0 的子数组个数
    # 构建转换后 nums 的前缀和 s，题目变成计算有多少对 (i, j) 满足 0 <= i < j <= n 且 s[j] − s[i] > 0
    # 枚举 j，题目变成计算 s 的下标区间 [0, j − 1] 中有多少个 s[i] < s[j]

    # 前缀和
    # 默认包含一个前缀和 0 ，表示空前缀
    sl = SortedList([0])
    ans = s = 0
    for x in nums:
        # 计算当前前缀和
        s += 1 if x == target else -1
        # 计算满足 s[i] < s[j] 的 i 个数
        ans += sl.bisect_left(s)
        # 将当前前缀和加入有序列表
        sl.add(s)
    return ans
